'''
Description: 
Author: Zilu
Date: 2021-11-04 13:30:13
Version: 
LastEditTime: 2021-11-04 13:41:40
LastEditors: Zilu
'''
# 函数内部可以调用自身
def fact(n):
    if n==1:
        return 1
    else:
        return n * fact(n-1)

fact(1)
fact(5)
fact(100)
fact(1000)      #栈溢出

# 解决递归调用栈溢出的方法是通过尾递归优化
# 尾递归是指，在函数返回的时候，调用自身本身，并且，return语句不能包含表达式。
# 这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。
def fact_fix(n):
    return fact_iter(n, 1)

def fact_iter(num,product):
    if num==1:
        return product
    else:
        return fact_iter(num-1,num*product)

fact_fix(1000)

# 尾递归调用时，如果做了优化，栈不会增长，因此，无论多少次调用也不会导致栈溢出。
# 遗憾的是，大多数编程语言没有针对尾递归做优化，Python解释器也没有做优化。
# 所以，即使把上面的fact(n)函数改成尾递归方式，也会导致栈溢出。

# 练习：汉诺塔
def move(n,a,b,c):
    if n==1:
        print(a,'-->',c)
    else:
        move(n-1,a,c,b)
        print(a,'-->',c)
        move(n-1,b,a,c)

move(3,'A','B','C')

